There is a method called wormhole routing as a method for transferring data between nodes in a parallel computer or the like. For example, PTL 1 describes a communication control device using wormhole routing as an inter-processor communication method. Further, PTL 2 describes a router for performing wormhole routing and its transfer method.
In wormhole routing, a buffer corresponding to one packet is provided in each port of a switch. Alternatively, a buffer corresponding to one block (also called a flit) to be transferred may be provided.
When a buffer of a transmission destination port becomes empty, a next packet is transferred toward the transmission destination port. Specifically, in wormhole routing, only one packet or only one flit at most is allowed to pass through one link connecting between ports at one time.
In the following, communication processing to be performed by using wormhole routing is described with reference to FIG. 22. FIG. 22 is an explanatory diagram illustrating an example of communication processing to be performed by using wormhole routing. Note that, in order to simplify description, one packet is handled as one flit.
A circle illustrated in FIG. 22 indicates a switch, and a rectangle illustrated in FIG. 22 indicates a terminal, respectively. Each terminal and each switch include one port or a plurality of ports. Further, each terminal and each switch are communicably connected to another terminal or another switch via a link connecting between ports. One straight line connecting a circle and a rectangle, or one straight line connecting between circles in FIG. 22 corresponds to one link.
A communication network illustrated in FIG. 22 is constituted by a switch 1 to a switch 9, a terminal 11 to a terminal 13, a terminal 17 to a terminal 19, and links. Further, a numeral including a prefix p such as p1 illustrated in FIG. 22 indicates a port number of a port of each switch and each terminal.
In the communication network illustrated in FIG. 22, a case is considered in which the terminal 11 transmits a packet to the terminal 17, and the terminal 12 transmits a packet to the terminal 18 respectively at a predetermined start timing. In order to simplify description, it is assumed that a time required for each packet to pass through each link is identical.
The terminal 12 transmits a packet A in such a manner that the packet A passes a route “terminal 12→switch 2→switch 5→switch 8→terminal 18”. A broken-lined arrow illustrated in FIG. 22 indicates movement of the packet A. Simultaneously, the terminal 11 transmits a packet B in such a manner that the packet B passes a route “terminal 11→switch 1→switch 2→switch 5→switch 7→terminal 17”. A solid-lined arrow illustrated in FIG. 22 indicates movement of the packet B.
When each terminal transmits a packet as illustrated in FIG. 22, the packet A and the packet B try to simultaneously pass through a link between the switch 2 and the switch 5. However, since only one packet is allowed to pass through one link at one time in wormhole routing as described above, in the present example, one of the packets stops at the switch 2.
A phenomenon that a packet being transferred stops in the course of transfer as described above is referred to as blocking. FIG. 22 illustrates that blocking occurs on a link between the switch 2 and the switch 5.
When blocking occurs, since a packet is not transferred as scheduled, communication delay occurs. Further, when blocking occurs in a part of a communication network, another packet may also stop due to an influence of the packet that stops by blocking. Consequently, blocking occurs in a chain reaction manner in a whole communication network.
Occurrence of blocking, and chain-reaction occurrence of blocking are fatal matters in a system for which promptness is required, such as an embedded system. For example, when communication delay occurs in an artificial satellite or a vehicle-mounted control device, a serious accident may occur.
In order to prevent occurrence of blocking, it is conceived that an order of communication is determined when communication processing using wormhole routing is designed. In the following, a method for generating a timeslot list in order to prevent occurrence of blocking when packets fail to simultaneously pass through a same network link in a communication network including a wormhole routing mechanism is described.
FIG. 23 is an explanatory diagram illustrating an example of a timeslot list. The timeslot list illustrated in FIG. 23 is constituted by communication management information. The communication management information is constituted by timeslots and communication routes. A timeslot and a communication route which are included in a same piece of communication management information have a relationship that communication associated with the communication route is started at a time corresponding to the timeslot. Note that each numeral in a communication route is associated with a switch or a terminal illustrated in FIG. 22.
For example, when a communication packet for an application which is introduced within an own terminal is transmitted, the terminal requests a timeslot management device or the like to perform communication in which the communication packet is transmitted. The timeslot management device which also receives a request for performing communication from another terminal manages communication by generating a timeslot list as illustrated in FIG. 23.
In a communication network to be managed by a timeslot management device, communication is performed based on a timeslot list generated by the timeslot management device. In an example of the timeslot list illustrated in FIG. 23, when a request for performing communication associated with a communication route “terminal 12→switch 2→switch 5→switch 8→terminal 18” is received, communication associated with a time corresponding to a timeslot 0 is started. Further, when a request for performing communication associated with a communication route “terminal 13→switch 3→switch 5→switch 7→terminal 17” is also received, communication associated with a time corresponding to a timeslot 0 is started.
When a time corresponding to a timeslot 0 has passed, next time, communication is performed based on communication management information in which a timeslot is 1. When times corresponding to a timeslot 1 to a timeslot 3 come, and a request for performing communication associated with a communication route indicated in a timeslot list is received, communication associated with each of the times is respectively started.
In a case where the timeslot list illustrated in FIG. 23 is used, when a time corresponding to a timeslot 9 has passed, communication is performed again based on communication management information in which a timeslot is 0. As described above, an order of performing communication is defined in a timeslot list.
Note that, since communication to be started at a time corresponding to each timeslot is not allocated from communication management information in which a timeslot is 4 to communication management information in which a timeslot is 9, a communication route in each piece of the communication management information is empty. Also in a timeslot list other than the timeslot list illustrated in FIG. 23, communication is not allocated to communication management information in which a communication route is empty.
FIG. 24 illustrates use timings for each link by each piece of communication to be performed based on the timeslot list illustrated in FIG. 23. FIG. 24 is a time chart illustrating use timings for each link by communication to be performed based on the timeslot list illustrated in FIG. 23.
A horizontal axis of the time chart illustrated in FIG. 24 is a timeslot axis associated with a timeslot, specifically, a time. Further, a vertical axis of the time chart illustrated in FIG. 24 is a link axis associated with a link within a communication network. For example, “1→2” in the link axis of the time chart illustrated in FIG. 24 indicates a link between the switch 1 and the switch 2 within the communication network illustrated in FIG. 22.
Each polygonal line within the time chart illustrated in FIG. 24 is associated with each piece of communication to be performed based on the timeslot list illustrated in FIG. 23. For example, in a polygonal line indicated by marks □ illustrated in FIG. 24, a mark □ is indicated at an intersection of a timeslot 2 and a link “1→2”.
The aforementioned mark □ indicates that communication associated with the polygonal line indicated by marks □ uses the link “1→2” during a period from a time corresponding to a timeslot 2 to a time corresponding to a timeslot 3. A diagram such as FIG. 24 is referred to as a time chart in the present specification. As described above, a time chart indicates a usage status of a communication link.
Other polygonal lines also indicate a content similar to the polygonal line indicated by marks □. As far as two or more marks are not indicated at a same position within a time chart, respective pieces of communication indicated in the time chart do not use a same link simultaneously. Specifically, blocking does not occur in respective pieces of communication indicated in a time chart.
A time when overall communication to be performed based on the timeslot list illustrated in FIG. 23 is finished is a time corresponding to a timeslot 9 being a time when communication using a link “switch 9→terminal 19” indicated by a mark x is finished, when referring to the time chart illustrated in FIG. 24.
The number of timeslots required until overall communication to be performed based on a timeslot list is completed is defined as a timeslot number of a timeslot list. Therefore, a timeslot number of the timeslot list illustrated in FIG. 23 is nine.
It is often the case that a timeslot list as illustrated in FIG. 23 is manually designed. However, a method for generating a timeslot list to be used in a wormhole routing network is also proposed. For example, NPL 1 describes a method for generating a timeslot list to be applied to a device.
FIG. 25 is a block diagram illustrating a configuration example of a timeslot list generation device described in NPL 1. As illustrated in FIG. 25, a timeslot list generation device 900 includes a shortest route generation means 910, a segment dividing means 920, and a segment timeslot allocation means 930.
As illustrated in FIG. 25, the shortest route generation means 910 receives network topology information and an endpoint pair list as an input. The endpoint pair list is constituted by endpoint pair information. Sets of inlet ports of a packet to be transferred by predetermined communication into a communication network, and outlet ports of the packet from the communication network are designated in the endpoint pair information.
The shortest route generation means 910 acquires a shortest route from an inlet port to an outlet port of each piece of communication by using network topology information and an endpoint pair list. Then, the shortest route generation means 910 generates a route list constituted by the acquired shortest routes.
Then, the segment dividing means 920 classifies routes within the route list generated by the shortest route generation means 910 into groups for each route which does not pass through a same link at all. A group of routes generated by the segment dividing means 920 is referred to as a segment.
Then, the segment timeslot allocation means 930 allocates one segment route to one piece of communication management information. FIG. 26 illustrates an example of a timeslot list to be generated by the timeslot list generation device 900. FIG. 26 is an explanatory diagram illustrating another example of the timeslot list. As described above, the respective routes allocated to a same piece of communication management information illustrated in FIG. 26 do not pass through a same link simultaneously.
Further, the segment timeslot allocation means 930 allocates each segment route as follows. First of all, the segment timeslot allocation means 930 allocates a first segment route to communication management information in which a timeslot is 0. As illustrated in FIG. 26, there are two routes allocated to communication management information in which a timeslot is 0.
Then, the segment timeslot allocation means 930 allocates a next segment route to communication management information of a timeslot succeeding to a timeslot corresponding to a time when overall communication associated with the previously allocated segment route is finished. A time when overall communication associated with routes allocated to communication management information in which a timeslot is 0 is finished corresponds to a timeslot 5.
Therefore, the segment timeslot allocation means 930 allocates a next segment route to communication management information in which a timeslot is 6. Likewise, the segment timeslot allocation means 930 allocates the remaining two segment routes to communication management information in which a timeslot is 13, and to communication management information in which a timeslot is 18, respectively.
Therefore, in a case of communication to be performed based on the timeslot list illustrated in FIG. 26, a communication group to be started during a same timeslot does not use a same link simultaneously. Further, other communication is not started until overall communication in a started communication group is finished. Therefore, when a timeslot list to be generated by a timeslot list generation device described in NPL 1 is used, communication free of blocking is performed.
FIG. 27 is a time chart illustrating use timings for each link by communication to be performed based on the timeslot list illustrated in FIG. 26. A time when overall communication to be performed based on the timeslot list illustrated in FIG. 26 is finished is a time corresponding to a timeslot 23, when referring to the time chart illustrated in FIG. 27. A time corresponding to a timeslot 23 is a time when communication using a link “switch 9→terminal 19” indicated by a mark ♦ in FIG. 27, and communication using a link “switch 7→terminal 17” indicated by a mark x in FIG. 27 are finished. Specifically, a timeslot number of the timeslot list illustrated in FIG. 26 is 23, which is larger than a timeslot number of the timeslot list illustrated in FIG. 23.